package day17;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CollectionsDemo {

	public static void main(String[] args) {
		List<String> list = new ArrayList<String>();
		list.add("bbb");
		list.add("cc");
		list.add("aa");
		list.add("eee");
		list.add("efgd");
		list.add("ddd");
		Collections.sort(list,new StringLengthComparator());
		//System.out.println("index" + binarySearch(list, "bb"));
		System.out.println("index=--->" + binarySearch(list, "cc",new StringLengthComparator()));
		System.out.println(list);
	}

	// 模拟Collections的binarySearch方法
	public static <T> int binarySearch(
			List<? extends Comparable<? super T>> list, T key) {
		int max = list.size() - 1, min = 0, mid;
		while (min <= max) {
			mid = (max + min) >> 1;
			Comparable<? super T> midValue = list.get(mid);
			int comp = midValue.compareTo(key);
			if (comp > 0) {
				max = mid - 1;
			} else if (comp < 0) {
				min = mid + 1;
			} else {
				return mid;
			}
		}
		return -(min + 1);
	}
	
	public static <T> int binarySearch(List<? extends T> list,T key, Comparator<? super T> c) {
		int max = list.size() -1 ,min = 0, mid;
		while (min <= max) {
			mid = (max +min ) >>1;
			T midValue = list.get(mid);
			int index = c.compare(midValue, key);
			if (index >0) {
				max = mid -1;
			} else if (index <0) {
				min = mid +1;
			} else {
				return mid;
			}
		}
		return -(min+1);
	}

}

//定义一个字符串长度的比较器
class StringLengthComparator implements Comparator<String> {

	@Override
	public int compare(String str1, String str2) {
		int num = str1.length() - str2.length();
		if (num == 0) {
			return str1.compareTo(str2);
		}
		return num;
	}
	
}


